﻿//30.串联所有单词的字串
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ans;

        unordered_map<string, int> hash1;

        int size = words.size();
        for (int i = 0; i < size; i++)
        {
            hash1[words[i]]++;
        }

        int len = words[0].size();
        for (int i = 0; i < len; i++)
        {
            unordered_map<string, int> hash2;
            for (int left = i, right = i, count = 0; right + len <= s.size(); right += len)
            {
                string in = s.substr(right, len);

                hash2[in]++;
                if (hash1.count(in) && hash2[in] <= hash1[in])
                {
                    count++;
                }

                if (count == size)
                {
                    ans.push_back(left);
                }

                if (right - left == (size - 1) * len)
                {
                    string out = s.substr(left, len);

                    if (hash1.count(out) && hash2[out] <= hash1[out])
                    {
                        count--;
                    }
                    hash2[out]--;

                    left += len;
                }


            }
        }

        return ans;
    }
};